home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / text / hyper / ADtoHT2_0.lha / MyLib.lha / stdlib / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-05  |  1.8 KB  |  56 lines
  1. #include <stdlib.h>
  2.  
  3. /************************************************************************/
  4.  
  5. /* sample compar function: int cmp(void *a,void *b){ return *(int *)a-*(int *)b; } */
  6.  
  7. /* This qsort function does a little trick:
  8.  * To reduce stackspace it iterates the larger interval instead of doing
  9.  * the recursion on both intervals. 
  10.  * So stackspace is limited to 32*stack_for_1_iteration = 
  11.  * 32*4*(4 arguments+1 returnaddress+11 stored registers) = 2048 Bytes,
  12.  * which is small enough for everybodys use.
  13.  * (And this is the worst case if you own 4GB and sort an array of chars.)
  14.  * Sparing the function calling overhead does improve performance, too.
  15.  */
  16.  
  17. void qsort
  18. (void *base,size_t nmemb,size_t size,int (*compar)(const void *,const void *))
  19. { char *base2=(char *)base;
  20.   char tmp;
  21.   size_t i,a,b,c;
  22.   while(nmemb>1)
  23.   { a=0;
  24.     b=nmemb-1;
  25.     c=(a+b)/2; /* Middle element */
  26.     for(;;)
  27.     { while((*compar)(&base2[size*c],&base2[size*a])>0) 
  28.         a++; /* Look for one >= middle */
  29.       while((*compar)(&base2[size*c],&base2[size*b])<0) 
  30.         b--; /* Look for one <= middle */
  31.       if(a>=b)
  32.         break; /* We found no pair */
  33.       for(i=0;i<size;i++) /* swap them */
  34.       { tmp=base2[size*a+i];
  35.         base2[size*a+i]=base2[size*b+i];
  36.         base2[size*b+i]=tmp; }
  37.       if(c==a) /* Keep track of middle element */
  38.         c=b;
  39.       else if(c==b)
  40.         c=a;
  41.       a++; /* These two are already sorted */
  42.       b--;
  43.     } /* a points to first element of right intervall now (b to last of left) */
  44.     b++;
  45.     if(b<nmemb-b) /* do recursion on smaller intervall and iteration on larger one */
  46.     { qsort(base2,b,size,compar);
  47.       base2=&base2[size*b];
  48.       nmemb=nmemb-b;
  49.     }
  50.     else
  51.     { qsort(&base2[size*b],nmemb-b,size,compar);
  52.       nmemb=b; }
  53.   }
  54.   return;
  55. }
  56.